/*
 * CopyRight(C) Kenbin
 */

#include "lws_utils.h"
#include "lws_hmm.h"
#include <ctime>
#include <cmath>
#include <cfloat>
#include <algorithm>

using namespace std;

namespace {
    enum { COUNT_SEG = 10000 };
}

LWS::CTrainHmm::CTrainHmm(int total_observe, int total_state)
{
    m_total_observe = total_observe;
    m_total_state = total_state;

    m_start_prob.resize(m_total_state);

    m_trans_prob.resize(m_total_state);
    for(int i = 0; i < m_total_state; i ++) {
	m_trans_prob[i].resize(m_total_state);
    }

    m_emit_prob.resize(m_total_observe);

    m_total_emits.resize(m_total_state);

    for(int i = 0; i < m_total_state; i ++) {
	m_start_prob[i] = 0;
	m_total_emits[i] = 0;
	for(int j = 0; j < m_total_state; j ++) {
	    m_trans_prob[i][j] = 0;
	}
    }
}

void LWS::CTrainHmm::TrainStartAndTrans(const char *corpus_file)
{
    ifstream cf(corpus_file);
    if(!cf)
    {
	cerr << "can't open the corpus file!" << endl;
	return;
    }

    unsigned long cnt = 0;
    clock_t last_clock = 0;
    double tt = 0;

    printf("train start and transfer probability ...\n");

    string line;
    while(getline(cf, line))
    {
	vector<pair<int, short> > os_pairs; /* a set of <observe, state> pair */
	convert_alineofcorpus(line, os_pairs);
	if(os_pairs.empty()) {
	    continue;
	}

	/* train start probability */
	short start_state = os_pairs[0].second;
	m_start_prob[start_state] ++;

	/* train transfer probability */
	for(unsigned i = 0; i < os_pairs.size()-1; i ++)
	{
	    short s1 = os_pairs[i].second;
	    short s2 = os_pairs[i+1].second;
	    if(s1 < 0 || s2 < 0) {
		continue;
	    }

	    m_trans_prob[s1][s2] ++;
	}

	cnt ++;
	if(cnt % COUNT_SEG == 0) {
	    clock_t cur_clock = clock();
	    double t = (double)(cur_clock - last_clock) / CLOCKS_PER_SEC;
	    tt += t;
	    last_clock = cur_clock;

	    printf("handle: %ld lines, time: %f s, totaltime: %f s\n", cnt, t, tt);
	}
    }

    float total_start = 0;
    for(int i = 0; i < m_total_state; i ++) {
	total_start += m_start_prob[i];
    }
    for(int i = 0; i < m_total_state; i ++) {
	m_start_prob[i] = (float)-log(m_start_prob[i] / total_start);
	if(m_start_prob[i] > 100) {
	    m_start_prob[i] = 100;
	}
    }

    float *total_trans = new float[m_total_state];
    for(int i = 0; i < m_total_state; i ++) {
	total_trans[i] = 0;
	for(int j = 0; j < m_total_state; j ++) {
	    total_trans[i] += m_trans_prob[i][j];
	}
    }
    for(int i = 0; i < m_total_state; i ++) {
	for(int j = 0; j < m_total_state; j ++) {
	    if(total_trans[i] == 0) {
		m_trans_prob[i][j] = 100;
	    } else {
		m_trans_prob[i][j] = (float)-log(m_trans_prob[i][j] / total_trans[i]);
		if(m_trans_prob[i][j] > 100) {
		    m_trans_prob[i][j] = 100;
		}
	    }
	}
    }
}

void LWS::CTrainHmm::TrainEmit(const char *corpus_file)
{
    ifstream cf(corpus_file);
    if(!cf)
    {
	cerr << "can't open the corpus file!" << endl;
	return;
    }

    unsigned long cnt = 0;
    clock_t last_clock = 0;
    double tt = 0;

    printf("train emit probability ...\n");

    string line;
    while(getline(cf, line))
    {
	vector<pair<int, short> > os_pairs;
	convert_alineofcorpus(line, os_pairs);
	if(os_pairs.empty()) {
	    continue;
	}

	/* train emit probability */
	for(unsigned i = 0; i < os_pairs.size(); i ++) {
	    int o = os_pairs[i].first;
	    short s = os_pairs[i].second;

	    if(o < 0 || s < 0) {
		continue;
	    }

	    m_emit_prob[o][s] ++;
	    m_total_emits[s] ++;
	}

	cnt ++;
	if(cnt % COUNT_SEG == 0) {
	    clock_t cur_clock = clock();
	    double t = (double)(cur_clock - last_clock) / CLOCKS_PER_SEC;
	    tt += t;
	    last_clock = cur_clock;

	    printf("handle: %ld lines, time: %f s, totaltime: %f s\n", cnt, t, tt);
	}
    }
}

void LWS::CTrainHmm::OutputStartAndTrans(const char *start_and_trans_file)
{
    ofstream stf(start_and_trans_file);

    for(int i = 0; i < m_total_state; i ++) {
	for(int j = 0; j < m_total_state; j ++) {
	    stf << m_trans_prob[i][j] << " ";
	}
	stf << endl;
    }

    for(int i = 0; i < m_total_state; i ++) {
	stf << m_start_prob[i] << " ";
    }
}

void LWS::CTrainHmm::OutputEmit(const char *emit_binfile, const char *emit_txtfile)
{
    ofstream ebf(emit_binfile, ios::binary);

    ebf.write((char *)&m_total_observe, sizeof(int));
    for(int i = 0; i < m_total_observe; i ++) {
	short state_count = m_emit_prob[i].size();
	ebf.write((char *)&state_count, sizeof(short));
	for(map<short, float>::iterator it = m_emit_prob[i].begin(); it != m_emit_prob[i].end(); ++ it) {
	    short s = it->first;
	    float emit_prob = it->second;
	    ebf.write((char *)&s, sizeof(short));
	    ebf.write((char *)&emit_prob, sizeof(float));
	}
    }

    ofstream etf(emit_txtfile);
    if(!etf)
    {
	cerr << "can't open the emit_txt file!" << endl;
	return;
    }

    for(int i = 0; i < m_total_observe; i ++) {
	for(map<short, float>::iterator it = m_emit_prob[i].begin(); it != m_emit_prob[i].end(); ++ it) {
	    etf << it->first << " " << it->second << " ";
	}
	etf << endl;
    }
}

LWS::CTrainPerson::CTrainPerson(int total_observe, int total_state)
    : CTrainHmm(total_observe, total_state)
{
}

void LWS::CTrainPerson::TrainEmit(const char *corpus_file)
{
    CTrainHmm::TrainEmit(corpus_file);

    ifstream cf(corpus_file);
    if(!cf)
    {
	cerr << "can't open the corpus file!" << endl;
	return;
    }

    string line;
    while(getline(cf, line))
    {
	vector<pair<string, string> > word_postag;
	Parse(line, word_postag);
	for(unsigned i = 0; i < word_postag.size(); i ++) {
	    if(word_postag[i].second == "nr") {
		m_person_name.insert(word_postag[i].first);
	    }
	}
    }

    for(set<string>::iterator it = m_person_name.begin(); it != m_person_name.end(); ++ it) {
	string person_name = *it;

	if(person_name.size() == 4) {
	    add_role(person_name, 0, PER_SURNAME);
	    add_role(person_name, 2, PER_GIVEN_SINGLE);
	} else if(person_name.size() == 6) {
	    add_role(person_name, 0, PER_SURNAME);
	    add_role(person_name, 2, PER_GIVEN_FIRST);
	    add_role(person_name, 4, PER_GIVEN_SECOND);
	} else if(person_name.size() > 6) {
	    add_role(person_name, 0, PER_TRANS_BEGIN);
	    for(unsigned i = 2; i < person_name.size()-2; i ++) {
		add_role(person_name, i, PER_TRANS_MIDDLE);
	    }
	    add_role(person_name, person_name.size()-2, PER_TRANS_END);
	}
    }

    for(int i = 0; i < m_total_observe; i ++) {
	for(map<short, float>::iterator it = m_emit_prob[i].begin(); it != m_emit_prob[i].end(); ++ it) {
	    it->second = (float)-log(it->second / m_total_emits[it->first]);
	}
    }

    for(int i = 0; i < m_total_observe; i ++) {
	if(m_emit_prob[i].empty()) {
	    m_emit_prob[i][OTHER] = 100;
	}
    }
}

void LWS::CTrainPerson::Output(const char *person_name_file)
{
    ofstream pf(person_name_file);

    for(set<string>::iterator it = m_person_name.begin(); it != m_person_name.end(); ++ it) {
	pf << *it << endl;
    }
}

void LWS::CTrainPerson::convert_alineofcorpus(string &line, vector<pair<int, short> >&os_pairs)
{
    os_pairs.clear();

    vector<pair<string, string> >word_postag;
    Parse(line, word_postag);
    for(unsigned i = 0; i < word_postag.size(); i ++) {
	/* atom segment */
	vector<string> atoms;
	string ASCII;
	for(unsigned j = 0; j < word_postag[i].first.size(); j ++) {
	    if(word_postag[i].first[j] < 0) {
		if(!ASCII.empty()) {
		    atoms.push_back(ASCII);
		    ASCII = "";
		}
		atoms.push_back(word_postag[i].first.substr(j++, 2));
	    } else {
		ASCII += word_postag[i].first[j];
	    }
	}
	if(!ASCII.empty()) {
	    atoms.push_back(ASCII);
	}

	vector<int> observe_idxs;
	for(unsigned j = 0; j < atoms.size(); j ++) {
	    observe_idxs.push_back(observe_index(atoms[j]));
	}

	if(word_postag[i].second == "nr") {
	    if(observe_idxs.size() == 1) {
		os_pairs.push_back(pair<int, short>(observe_idxs[0], OTHER));
	    } else if(observe_idxs.size() == 2) {
		os_pairs.push_back(pair<int, short>(observe_idxs[0], PER_SURNAME));
		os_pairs.push_back(pair<int, short>(observe_idxs[1], PER_GIVEN_SINGLE));
	    } else if(observe_idxs.size() == 3) {
		os_pairs.push_back(pair<int, short>(observe_idxs[0], PER_SURNAME));
		os_pairs.push_back(pair<int, short>(observe_idxs[1], PER_GIVEN_FIRST));
		os_pairs.push_back(pair<int, short>(observe_idxs[2], PER_GIVEN_SECOND));
	    } else if(observe_idxs.size() > 3) {
		os_pairs.push_back(pair<int, short>(observe_idxs[0], PER_TRANS_BEGIN));
		for(unsigned j = 1; j < observe_idxs.size()-1; j ++) {
		    os_pairs.push_back(pair<int, short>(observe_idxs[j], PER_TRANS_MIDDLE));
		}
		os_pairs.push_back(pair<int, short>(observe_idxs[observe_idxs.size()-1], PER_TRANS_END));
	    }
	} else {
	    for(unsigned j = 0; j < observe_idxs.size(); j ++) {
		os_pairs.push_back(pair<int, short>(observe_idxs[j], OTHER));
	    }
	}
    }

    for(int i = 1; i < os_pairs.size()-1; i ++) {
	short pre_role = os_pairs[i-1].second;
	short cur_role = os_pairs[i].second;
	short next_role = os_pairs[i+1].second;

	if(cur_role == PER_SURNAME && pre_role == OTHER) {
	    os_pairs[i-1].second = PER_PRE;
	} else if(cur_role == PER_TRANS_BEGIN && pre_role == OTHER) {
	    os_pairs[i-1].second = PER_PRE;
	} else if(cur_role == PER_GIVEN_SINGLE && next_role == OTHER) {
	    os_pairs[i+1].second = PER_NEXT;
	} else if(cur_role == PER_GIVEN_SECOND && next_role == OTHER) {
	    os_pairs[i+1].second = PER_NEXT;
	} else if(cur_role == PER_TRANS_END && next_role == OTHER) {
	    os_pairs[i+1].second = PER_NEXT;
	}
    }
}

void LWS::CTrainPerson::add_role(string &person_name, int pos, int role_tag)
{
    string CHAR = person_name.substr(pos, 2);
    m_emit_prob[observe_index(CHAR)][role_tag] ++;
    m_total_emits[role_tag] ++;
}

int LWS::CTrainPerson::observe_index(string &observe_desc)
{
    if(observe_desc.size() < 2) {
	return m_total_observe - 1;
    } else {
	int idx = GB2312HanziIndex(observe_desc);
	if(idx >= 0 && idx < 6768) {
	    return idx;
	} else {
	    return m_total_observe - 1;
	}
    }
}

LWS::CTrainLocation::CTrainLocation(int total_observe, int total_state)
    : CTrainHmm(total_observe, total_state)
{
}

void LWS::CTrainLocation::TrainEmit(const char *corpus_file)
{
    CTrainHmm::TrainEmit(corpus_file);

    ifstream cf(corpus_file);
    if(!cf)
    {
	cerr << "can't open the corpus file!" << endl;
	return;
    }

    string line;
    while(getline(cf, line))
    {
	vector<pair<string, string> > word_postag;
	Parse(line, word_postag);
	for(unsigned i = 0; i < word_postag.size(); i ++) {
	    if(word_postag[i].second == "ns") {
		m_location_name.insert(word_postag[i].first);
	    }
	}
    }

    for(set<string>::iterator it = m_location_name.begin(); it != m_location_name.end(); ++ it) {
	string location_name = *it;
	if(location_name.size() >= 4) {
	    add_role(location_name, 0, LOC_BEGIN);
	    for(unsigned i = 2; i < location_name.size()-2; i ++) {
		add_role(location_name, i, LOC_MIDDLE);
	    }
	    add_role(location_name, location_name.size()-2, LOC_END);
	}
    }

    for(int i = 0; i < m_total_observe; i ++) {
	for(map<short, float>::iterator it = m_emit_prob[i].begin(); it != m_emit_prob[i].end(); ++ it) {
	    it->second = (float)-log(it->second / m_total_emits[it->first]);
	}
    }

    for(int i = 0; i < m_total_observe; i ++) {
	if(m_emit_prob[i].empty()) {
	    m_emit_prob[i][OTHER] = 100;
	}
    }
}

void LWS::CTrainLocation::Output(const char *location_name_file)
{
    ofstream lf(location_name_file);

    for(set<string>::iterator it = m_location_name.begin(); it != m_location_name.end(); ++ it) {
	lf << *it << endl;
    }
}

void LWS::CTrainLocation::convert_alineofcorpus(string &line, vector<pair<int, short> >&os_pairs)
{
    os_pairs.clear();

    vector<pair<string, string> >word_postag;
    Parse(line, word_postag);
    for(unsigned i = 0; i < word_postag.size(); i ++) {
	/* atom segment */
	vector<string> atoms;
	string ASCII;
	for(unsigned j = 0; j < word_postag[i].first.size(); j ++) {
	    if(word_postag[i].first[j] < 0) {
		if(!ASCII.empty()) {
		    atoms.push_back(ASCII);
		    ASCII = "";
		}
		atoms.push_back(word_postag[i].first.substr(j++, 2));
	    } else {
		ASCII += word_postag[i].first[j];
	    }
	}
	if(!ASCII.empty()) {
	    atoms.push_back(ASCII);
	}

	vector<int> observe_idxs;
	for(unsigned j = 0; j < atoms.size(); j ++) {
	    observe_idxs.push_back(observe_index(atoms[j]));
	}

	if(word_postag[i].second == "ns") {
	    if(observe_idxs.size() == 1) {
		os_pairs.push_back(pair<int, short>(observe_idxs[0], OTHER));
	    } else if(observe_idxs.size() >= 2) {
		os_pairs.push_back(pair<int, short>(observe_idxs[0], LOC_BEGIN));
		for(unsigned j = 1; j < observe_idxs.size()-1; j ++) {
		    os_pairs.push_back(pair<int, short>(observe_idxs[j], LOC_MIDDLE));
		}
		os_pairs.push_back(pair<int, short>(observe_idxs[observe_idxs.size()-1], LOC_END));
	    }
	} else {
	    for(unsigned j = 0; j < observe_idxs.size(); j ++) {
		os_pairs.push_back(pair<int, short>(observe_idxs[j], OTHER));
	    }
	}
    }

    for(int i = 1; i < os_pairs.size()-1; i ++) {
	short pre_role = os_pairs[i-1].second;
	short cur_role = os_pairs[i].second;
	short next_role = os_pairs[i+1].second;

	if(cur_role == LOC_BEGIN && pre_role == OTHER) {
	    os_pairs[i-1].second = LOC_PRE;
	} else if(cur_role == LOC_END && next_role == OTHER) {
	    os_pairs[i+1].second = LOC_NEXT;
	}
    }
}

void LWS::CTrainLocation::add_role(string &person_name, int pos, int role_tag)
{
    string CHAR = person_name.substr(pos, 2);
    m_emit_prob[observe_index(CHAR)][role_tag] ++;
    m_total_emits[role_tag] ++;
}

int LWS::CTrainLocation::observe_index(string &observe_desc)
{
    if(observe_desc.size() < 2) {
	return m_total_observe - 1;
    } else {
	int idx = GB2312HanziIndex(observe_desc);
	if(idx >= 0 && idx < 6768) {
	    return idx;
	} else {
	    return m_total_observe - 1;
	}
    }
}

LWS::CTrainPosTag::CTrainPosTag(const char *word_file, const char *postag_file, int total_observe, int total_state)
    : CTrainHmm(total_observe, total_state)
{
    ifstream df(word_file);
    if(!df)
    {
	cerr << "can't open the word file!" << endl;
	return;
    }

    string word;
    int word_freq;
    int word_id = 0;

    while(df >> word && df >> word_freq) {
	m_word_wordid[word] = word_id ++;
    }

    ifstream pf(postag_file);
    if(!pf)
    {
	cerr << "can't open the postag file!" << endl;
	return;
    }

    string postag;
    int postag_idx = 0;

    while(pf >> postag) {
	m_postag_posidx[postag] = postag_idx ++;
    }
}

void LWS::CTrainPosTag::TrainEmit(const char *corpus_file)
{
    CTrainHmm::TrainEmit(corpus_file);

    for(int i = 0; i < m_total_observe; i ++) {
	for(map<short, float>::iterator it = m_emit_prob[i].begin(); it != m_emit_prob[i].end(); ++ it) {
	    it->second = (float)-log(it->second / m_total_emits[it->first]);
	}
    }

    map<short, float> number;
    number[m] = 100;
    m_emit_prob.push_back(number);

    map<short, float> times;
    times[t] = 100;
    m_emit_prob.push_back(times);

    map<short, float> person_name;
    person_name[nr] = 100;
    m_emit_prob.push_back(person_name);

    map<short, float> location_name;
    location_name[ns] = 100;
    m_emit_prob.push_back(location_name);

    map<short, float> unknown;
    unknown[nx] = 100;
    m_emit_prob.push_back(unknown);

    m_total_observe = m_emit_prob.size();

    for(int i = 0; i < m_total_observe; i ++) {
	if(m_emit_prob[i].empty()) {
	    m_emit_prob[i][nx] = 100;
	}
    }
}

void LWS::CTrainPosTag::convert_alineofcorpus(string &line, vector<pair<int, short> >&os_pairs)
{
    os_pairs.clear();

    vector<pair<string, string> >word_postag;
    Parse(line, word_postag);
    for(unsigned i = 0; i < word_postag.size(); i ++) {
	pair<int, short> observe_state;
	observe_state.first = observe_index(word_postag[i].first);
	observe_state.second = postag_index(word_postag[i].second);
	os_pairs.push_back(observe_state);
    }
}

int LWS::CTrainPosTag::observe_index(string &observe_desc)
{
    if(m_word_wordid.find(observe_desc) != m_word_wordid.end()) {
	return m_word_wordid[observe_desc];
    } else {
	return -1;
    }
}

int LWS::CTrainPosTag::postag_index(string &postag_desc)
{
    if(m_postag_posidx.find(postag_desc) != m_postag_posidx.end()) {
	return m_postag_posidx[postag_desc];
    } else {
	return -1;
    }
}

bool LWS::CHmm::LoadStartAndTrans(const char *start_and_trans_file, int total_state)
{
    m_total_state = total_state;

    m_start_prob.resize(total_state);

    m_trans_prob.resize(total_state);
    for(int i = 0; i < total_state; i ++) {
	m_trans_prob[i].resize(total_state);
    }

    ifstream stf(start_and_trans_file);
    if(!stf)
    {
	cerr << "can't open the start and trans file!" << endl;
	return false;
    }

    for(int i = 0; i < total_state; i ++) {
	for(int j = 0; j < total_state; j ++) {
	    stf >> m_trans_prob[i][j];
	}
    }

    for(int i = 0; i < total_state; i ++) {
	stf >> m_start_prob[i];
    }

    return true;
}

bool LWS::CHmm::LoadEmit(const char *emit_binfile)
{
    ifstream ef(emit_binfile);
    if(!ef)
    {
	cerr << "can't open the emit binfile!" << endl;
	return false;
    }

    ef.read((char *)&m_total_observe, sizeof(int));
    m_emit_prob.resize(m_total_observe);
    for(int i = 0; i < m_total_observe; i ++) {
	short state_count;
	ef.read((char *)&state_count, sizeof(short));
	m_emit_prob[i].resize(state_count);
	for(int j = 0; j < state_count; j ++) {
	    ef.read((char *)&m_emit_prob[i][j].state, sizeof(short));
	    ef.read((char *)&m_emit_prob[i][j].emit_prob, sizeof(float));
	}
    }

    return true;
}

float LWS::CHmm::StartProb(short state)
{
    return state < m_total_state ? m_start_prob[state] : -1;
}

float LWS::CHmm::TransProb(short state1, short state2)
{
    if(state1 >= m_total_state || state2 >= m_total_state) {
	return -1;
    } else {
	return m_trans_prob[state1][state2];
    }
}

float LWS::CHmm::EmitProb(int observe, short state)
{
    if(observe >= m_total_observe || state >= m_total_state) {
	return -1;
    } else {
	int state_count = m_emit_prob[observe].size();
	for(int i = 0; i < state_count; i ++) {
	    if(state == m_emit_prob[observe][i].state) {
		return m_emit_prob[observe][i].emit_prob;
	    }
	}
    }

    return -1;
}

int LWS::CHmm::StateCount(int observe)
{
    return m_emit_prob[observe].size();
}

short LWS::CHmm::StateOfObserve(int observe, int idx)
{
    if(observe >= m_total_observe) {
	return -1;
    } else if(idx >= m_emit_prob[observe].size()) {
	return -1;
    } else {
	return m_emit_prob[observe][idx].state;
    }
}

float LWS::CHmm::EmitProbOfObserve(int observe, int idx)
{
    if(observe >= m_total_observe) {
	return -1;
    } else if(idx >= m_emit_prob[observe].size()) {
	return -1;
    } else {
	return m_emit_prob[observe][idx].emit_prob;
    }
}

LWS::CHmmAlgo::CHmmAlgo(CHmm *hmm) : m_hmm(hmm)
{
}

float LWS::CHmmAlgo::GetTransProb(short state1, short state2)
{
    return m_hmm->TransProb(state1, state2);
}

float LWS::CHmmAlgo::GetEmitProb(int observe, short state)
{
    return m_hmm->EmitProb(observe, state);
}

void LWS::CHmmAlgo::GetBestStateSequence(vector<int> &observes, vector<short> &best_states)
{
    int observe_count = observes.size();
    if(observe_count > 0) {
	/* init path net */
	m_path_net.resize(observe_count);
	for(int i = 0; i < observe_count; i ++) {
	    int observe = observes[i];
	    int state_count = m_hmm->StateCount(observe);

	    m_path_net[i].resize(state_count);

	    for(int j = 0; j < state_count; j ++) {
		m_path_net[i][j].pre = -1;
		m_path_net[i][j].state = m_hmm->StateOfObserve(observe, j);
		m_path_net[i][j].accum_prob = m_hmm->EmitProbOfObserve(observe, j);
	    }
	}

	/* viterbi */
	for(int i = 0; i < m_path_net[0].size(); i ++) {
	    m_path_net[0][i].accum_prob += m_hmm->StartProb(m_path_net[0][i].state);
	}

	for(int i = 1; i < observe_count; i ++) {
	    for(int j = 0; j < m_path_net[i].size(); j ++) {
		float emit_prob = m_path_net[i][j].accum_prob;
		m_path_net[i][j].accum_prob = FLT_MAX;
		for(int k = 0; k < m_path_net[i-1].size(); k ++) {
		    int pre_state = m_path_net[i-1][k].state;
		    int cur_state = m_path_net[i][j].state;
		    float prob = m_path_net[i-1][k].accum_prob + emit_prob
			+ m_hmm->TransProb(pre_state, cur_state);
		    if(prob < m_path_net[i][j].accum_prob) {
			m_path_net[i][j].accum_prob = prob;
			m_path_net[i][j].pre = k;
		    }
		}
	    }
	}

	/* generate best states sequence */
	float max_prob = FLT_MAX;
	int last;
	for(int i = 0; i < m_path_net[observe_count-1].size(); i ++) {
	    if(m_path_net[observe_count-1][i].accum_prob < max_prob) {
		max_prob = m_path_net[observe_count-1][i].accum_prob;
		last = i;
	    }
	}

	for(int i = observe_count-1, j = last; i >=0; i --) {
	    best_states.push_back(m_path_net[i][j].state);
	    j = m_path_net[i][j].pre;
	}

	reverse(best_states.begin(), best_states.end());
    }
}
